import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NQueens0104_51 {

    List<List<String>> result = new ArrayList<>();

    int row = 0;

    public List<List<String>> solveNQueens(int n) {

        char[][] chessboard = new char[n][n];
        for (char[] chars : chessboard) {
            Arrays.fill(chars,'.');
        }

        backTracking(chessboard,n,row);
        return result;
    }

    private void backTracking(char[][] chessboard, int n, int row) {
        if(row == n) {
            result.add(array2List(chessboard));
            return;
        }

        for (int i = 0; i < n; i++) {
            if(isValid(chessboard,n,row,i)){
                chessboard[row][i] = 'Q';
                backTracking(chessboard,n,row+1);
                chessboard[row][i] = '.'; //回溯
            }
        }
    }

    private boolean isValid(char[][] chessboard, int n, int row, int i) {

        //不用检查 行，因为回溯

        //列
        for (int j = 0; j < row; j++) {
            if(chessboard[j][i] == 'Q') return false;
        }

        //斜45
        for (int j = row - 1, m = i-1; j>=0 && m >=0; j--, m--) {
            if(chessboard[j][m] == 'Q') return false;
        }

        //斜135
        for (int j = row - 1, m = i+1; j >=0 && m < n; j--, m++) {
            if(chessboard[j][m] == 'Q') return false;
        }
        return true;

    }

    private List<String> array2List(char[][] chessboard) {
        List<String> res = new ArrayList<>();
        for (char[] chars : chessboard) {
            res.add(String.valueOf(chars));
        }
        return res;
    }

}
